Search results for "Cyclic permutation"

Quantum lower bound for inverting a permutation with advice

2014

Given a random permutation $f: [N] \to [N]$ as a black box and $y \in [N]$, we want to output $x = f^{-1}(y)$. Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but \emph{not} on the input $y$. Classically, there is a data structure of size $\tilde{O}(S)$ and an algorithm that with the help of the data structure, given $f(x)$, can invert $f$ in time $\tilde{O}(T)$, for every choice of parameters $S$, $T$, such that $S\cdot T \ge N$. We prove a quantum lower bound of $T^2\cdot S \ge \tilde{\Omega}(\epsilon N)$ for quantum algorithms that invert a random permutation $f$ on an $\epsilon$ fraction of…

Permutation properties and the fibonacci semigroup

1989

On finite products of totally permutable groups

1996

In this paper the structure of finite groups which are the product of two totally permutable subgroups is studied. In fact we can obtain the -residual, where is a formation, -projectors and -normalisers, where is a saturated formation, of the group from the corresponding subgroups of the factor subgroups.

Cyclic and lift closures for k…21-avoiding permutations

2011

We prove that the cyclic closure of the permutation class avoiding the pattern k(k-1)...21 is finitely based. The minimal length of a minimal permutation is 2k-1 and these basis permutations are enumerated by (2k-1).c"k where c"k is the kth Catalan number. We also define lift operations and give similar results. Finally, we consider the toric closure of a class and we propose some open problems.

Statistics-preserving bijections between classical and cyclic permutations

2012

Recently, Elizalde (2011) [2] has presented a bijection between the set C"n"+"1 of cyclic permutations on {1,2,...,n+1} and the set of permutations on {1,2,...,n} that preserves the descent set of the first n entries and the set of weak excedances. In this paper, we construct a bijection from C"n"+"1 to S"n that preserves the weak excedance set and that transfers quasi-fixed points into fixed points and left-to-right maxima into themselves. This induces a bijection from the set D"n of derangements to the set C"n"+"1^q of cycles without quasi-fixed points that preserves the weak excedance set. Moreover, we exhibit a kind of discrete continuity between C"n"+"1 and S"n that preserves at each s…

Transitive permutation groups in which all derangements are involutions

2006

AbstractLet G be a transitive permutation group in which all derangements are involutions. We prove that G is either an elementary abelian 2-group or is a Frobenius group having an elementary abelian 2-group as kernel. We also consider the analogous problem for abstract groups, and we classify groups G with a proper subgroup H such that every element of G not conjugate to an element of H is an involution.

Finitary Representations and Images of Transitive Finitary Permutation Groups

1999

Abstract We characterize the point stabilizers and kernels of finitary permutation representations of infinite transitive groups of finitary permutations. Moreover, the number of such representations is determined.

Multiply Transitive Permutation Groups

1982

Since the beginnings of finite group theory, the multiply transitive permutation groups have exercised a certain fascination. This is mainly due to the fact that apart from the symmetric and alternating groups not many of them were known. Only very recently final results about multiply transitive permutation groups have been proved, using the classification of all finite simple groups (see 7.5).